import java.util.*;;
/**
 * 
 * 数据流中的中位数
 * 描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足 
1
≤
n
≤
1000
 
1≤n≤1000  ，大小满足 
1
≤
v
a
l
≤
1000
 
1≤val≤1000 

进阶： 空间复杂度 
O
(
n
)
 
O(n)  ， 时间复杂度 
O
(
n
l
o
g
n
)
 
O(nlogn) 
 */
public class 数据流中的中位数 {
    
    public static void main(String[] args) {

        int[] nums = new int[]{5,2,3,4,1,6,7,0,8};

        for(int num : nums){

            Insert(num);
        }

        resultList.stream().map(s -> s+", ").forEach(System.out::print);
        System.out.println();

    }

    private static List<Integer> addList = new ArrayList<>();
    private static List<Double> resultList = new ArrayList<>();

    public static void Insert(Integer num) {
    
        addList.add(num);
        GetMedian();
    }

    public static Double GetMedian() {

        if(null!=addList && !addList.isEmpty()){

            //排序
            addList.sort((a, b) -> b - a);

            if(addList.size() % 2 !=0){

                //取中间值
                double result = addList.get((addList.size()-1) / 2) / 1.0D;
                resultList.add(result);
                return result;

            } else {
                int pre = addList.get(addList.size()/2 -1);
                int next = addList.get(addList.size()/2);

                double result = (pre + next) / 2.0D;
                resultList.add(result);
                return result;

            }

        }

        return -1D;
    }
}
